package alo.p6.work5;

import alo.p6.AVLTreeNode;

/**
 * @ClassName Rotate
 * @Description 平衡二叉树的旋转
 * @Author Fanxc
 * @DATE 2021/3/4 14:46
 * @Version 1.0
 */
public class Rotate {
    //左旋
    AVLTreeNode singleRotateLeft(AVLTreeNode X){
        Height Height = new Height();
        AVLTreeNode W=X.getLeft();
        X.setLeft(W.getRight());
        W.setRight(X);
        X.setHeight(Math.max(Height.height(X.getLeft()),Height.height(X.getRight()))+1);
        W.setHeight(Math.max(Height.height(W.getLeft()),X.getHeight())+1);
        return W;
    }
    //右旋
    AVLTreeNode singleRotateRight(AVLTreeNode X){
        Height Height = new Height();
        AVLTreeNode W=X.getRight();
        X.setRight(W.getLeft());
        W.setLeft(X);
        X.setHeight(Math.max(Height.height(X.getLeft()),Height.height(X.getRight()))+1);
        W.setHeight(Math.max(Height.height(W.getRight()),X.getHeight())+1);
        return W;
    }
    //左平衡旋转
    //左孩子右旋、根结点左旋
    AVLTreeNode doubleRotateWithLeft(AVLTreeNode Z){
        Z.setLeft(singleRotateRight(Z.getLeft()));
        return singleRotateLeft(Z);
    }

    //右平衡旋转
    //右孩子左旋、根结点右旋
    AVLTreeNode doubleRotateWithRight(AVLTreeNode Z){
        Z.setRight(singleRotateLeft(Z.getRight()));
        return singleRotateRight(Z);
    }
}
